package com.njupt.HashTable;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/*

383. 赎金信
 */
public class CanConstruct {

    //错解
    public boolean canConstruct1(String ransomNote, String magazine) {

        if (ransomNote.length()>magazine.length()){
            return false;
        }

        Set<Character> set = new HashSet<>();
        for (int i = 0; i < ransomNote.length(); i++) {
            set.add(ransomNote.charAt(i));
        }

        Iterator<Character> iterator = set.iterator();
        while (iterator.hasNext()){
            Character next = iterator.next();
            if(!magazine.contains(String.valueOf(next))){
                return false;
            }
        }
        return true;
    }
    //正解，ransomNote中的每个字符，之只能在magazine中出现一次
    public boolean canConstruct(String ransomNote, String magazine) {

        if (ransomNote.length()>magazine.length()){
            return false;
        }

        int[] recordR = new int[26];
        int[] recordM = new int[26];

        for (int i = 0; i < ransomNote.length(); i++) {
            recordR[ransomNote.charAt(i)-'a']++;
        }
        System.out.println();

        for (int i = 0; i < magazine.length(); i++) {
            recordM[magazine.charAt(i)-'a']++;
        }

        for (int i = 0; i < recordR.length; i++) {
            if(recordR[i]>recordM[i]){
                return false;
            }
        }
        return true;
    }

    /**
     * 哈希法 最优解。要判断一个元素是否出现过要考虑使用哈希法
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct2(String ransomNote, String magazine) {
        int[] result = new int[26];

        if(ransomNote.length() > magazine.length()){
            return false;
        }

        for (int i = 0; i < magazine.length(); i++) {
            result[magazine.charAt(i) -'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            result[ransomNote.charAt(i) - 'a']--;
            if(result[ransomNote.charAt(i) - 'a']<0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String ransomNote = "fihjjjjei";
        String magazine = "hjibagacbhadfaefdjaeaebgi";

        CanConstruct test = new CanConstruct();
        System.out.println(test.canConstruct2(ransomNote, magazine));

    }
}
